package offer;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */

public class MergeTwoLists {

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        listNode1.next = new ListNode(2);
        listNode1.next.next = new ListNode(6);
        listNode1.next.next.next = new ListNode(8);

        ListNode listNode2 = new ListNode(1);
        listNode2.next = new ListNode(5);
        listNode2.next.next = new ListNode(7);
        listNode2.next.next.next = new ListNode(9);
        ListNode listNode = new MergeTwoLists().recursion(listNode1, listNode2);
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        return recursion(l1, l2);
    }

    private ListNode recursion(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {//1.结束条件
            return l1 == null ? l2 : l1;
        }
        //2.转换成子问题
        ListNode res;
        if (l1.val > l2.val) {
            res = new ListNode(l2.val);
            res.next = recursion(l1, l2.next);
        } else {
            res = new ListNode(l1.val);
            res.next = recursion(l1.next, l2);
        }
        return res;
    }

    public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) {
            return null;
        } else if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        }
        ListNode res = null;
        ListNode curr = null;
        while (l1 != null && l2 != null) {
            if (res == null) {
                if (l1.val >= l2.val) {
                    res = new ListNode(l2.val);
                    l2 = l2.next;
                } else {
                    res = new ListNode(l1.val);
                    l1 = l1.next;
                }
                curr = res;
            } else {
                if (l1.val >= l2.val) {
                    curr.next = new ListNode(l2.val);
                    l2 = l2.next;
                } else {
                    curr.next = new ListNode(l1.val);
                    l1 = l1.next;
                }
                curr = curr.next;
            }
        }
        if (l1 == null) {
            curr.next = l2;
            curr = curr.next;
        }
        if (l2 == null) {
            curr.next = l1;
        }
        return res;
    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
